package com.zjj.algorithm.learning.leetcode.array;

import java.util.*;

/**
 * 15. 三数之和 中等题目
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * <p>
 * 你返回所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * 示例 3：
 * <p>
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 *
 * @author zjj_admin
 * @date 2022/11/2 11:53
 */
public class ThreeNumSum {


    public static void main(String[] args) {
        int[] nums = new int[]{34, 55, 79, 28, 46, 33, 2, 48, 31, -3, 84, 71, 52, -3, 93, 15, 21, -43, 57, -6, 86, 56, 94, 74, 83, -14, 28, -66, 46, -49, 62, -11, 43, 65, 77, 12, 47, 61, 26, 1, 13, 29, 55, -82, 76, 26, 15, -29, 36, -29, 10, -70, 69, 17, 49};
        int[] nums2 = new int[]{-1, 0, 1, 2, -1, -4};
        int[] nums3 = new int[]{0, 0, 0};
        List<List<Integer>> lists = threeSum2(nums2);
        System.out.println(lists.toString());


    }


    /**
     * 暴力方法
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        if (nums.length < 3) {
            return lists;
        }
        for (int i = 0; i <= nums.length - 3; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                for (int k = i + 1; k < j; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[k]);
                        list.add(nums[j]);
                        list.add(nums[i]);
                        lists.add(list);
                        break;
                    }
                }
            }
        }
        List<List<Integer>> newList = new ArrayList<>();
        Set<String> set = new HashSet<>();
        for (List<Integer> integers : lists) {
            Collections.sort(integers);
            String s = integers.toString();
            if (!set.contains(s)) {
                set.add(s);
                newList.add(integers);
            }
        }
        return newList;
    }


    /**
     * 先排序，再计较查找
     * 时间
     * 19 ms
     * 击败
     * 91.43%
     * 内存
     * 45.7 MB
     * 击败
     * 35.98%
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        if (nums.length < 3) {
            return lists;
        }
        //先进行排序
        Arrays.sort(nums);
        int l;
        int r;
        int sum;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > 0) {
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            l = i + 1;
            r = nums.length - 1;
            while (l < r) {
                sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    lists.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //去重
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                }
            }
        }
        return lists;
    }

}
